package com.ly.algorithm.DataStructures.sort;

import java.util.Date;
import java.util.Random;

/**
 * @Classname HeapSort
 * @Description TODO
 * @Date 2020/5/2 16:09
 * @Author 冷心影翼
 */
public class HeapSort {

    public void sort(int[] arr) {
        for(int i=arr.length/2-1;i>=0;i--) {
            adjustHeap(arr,i,arr.length);
        }

        int temp;
        for(int i=arr.length-1;i>0;i--) {
            temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            adjustHeap(arr,0,i);
        }
    }

    public void adjustHeap(int[] arr,int i,int length) {
        int temp = arr[i];
        for(int k=i*2+1;k<length;k = k * 2 +1) {
            if(k+1<length && arr[k] < arr[k+1] ) {
                k++;
            }
            if(arr[k] > temp ) {
                arr[i] = arr[k];
                i = k;
            }else {
                break;
            }
        }
        arr[i] = temp;
    }
}

class Test {

    public static void main(String[] args) {
        HeapSort heapSort = new HeapSort();
//        int[] arr = {4,6,8,5,9,7,7,11,27};
        int[] arr = new int[800000];

        for(int i=0;i<800000;i++) {
            arr[i] = new Random().nextInt(800000);
        }
        Date date1 = new Date();
        heapSort.sort(arr);
        Date date2 = new Date();
        System.out.println(date2.getTime()-date1.getTime());
    }
}

